package five;

public class A084 {

    //
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if(n<2) return;
        int k=-1,j=n-1;
        //1.找到第一组逆序的
        for(;j>0;j--) {
            if(nums[j]>nums[j-1]) {
                k=j-1;
                break;
            }
        }
        //2.降序序列
        if(k==-1) {
            reverse(nums,0,n-1);
            return;
        }
        //3.交换k和
        for(int i=n-1;i>=j;i--) {
            if(nums[i]>nums[k]) {
                int t = nums[i];
                nums[i] = nums[k];
                nums[k] = t;
                break;
            }
        }
        //4.逆序后面的内容[j,n-1]
        reverse(nums,j,n-1);
    }
    //逆序[i,j]
    public void reverse(int[] nums,int i,int j) {
        while(i<j) {
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
            i++;
            j--;
        }

    }

}
